Under certain conditions, it is desirable to allow multiple concurrent processes to have shared access to a group of shared memory structures. For example, a database server may be implemented by numerous processes, where many of the processes require shared access to data located in a memory associated with the database server. Typically the memory area that contains the shared data of the database server is allocated by an operating system as a logically contiguous region. The shared memory area is not necessarily a physically contiguous region, but rather represents a contiguous range of virtual memory address space. The contiguous range of virtual address space may include one or more noncontiguous regions of physical memory.
For a database server, the items stored in the shared memory area typically include parse trees and execution plans for individual queries, and compiled byte code and constant pools for stored program units that can be executed by server processes. Such programs may be, for example, PL/SQL.TM. programs which have been compiled into byte code that is interpreted by a PL/SQL.TM. interpreter. PL/SQL.TM. is a procedural database language available from Oracle Corporation.
Currently, whenever an item needs to be stored in the shared memory area, the item is preferably allocated an unused contiguous area in the shared memory area that is large enough to hold the entire item. To make an area of the required size available when an unused area of the required size is not available, one or more items currently residing in the shared memory area are removed. Over time, as items are stored in the shared memory area and removed to be replaced by other items, the shared memory area address space becomes fragmented, i.e. contains many small non-contiguous unused areas, as opposed to a few large unused areas.
Fragmentation of the shared memory area is a serious problem. It increases the likelihood that whenever a new item is stored in the shared memory area, one or more items currently in the shared memory area are removed, despite the fact that in total, the unused area in the shared memory area address space might have been large enough to accommodate the newly stored item.
Consequently, fragmentation adversely impacts performance. Fragmentation causes old items to be removed from the shared memory area to make room for new items, where the old items would not have to have been removed if the shared memory area was not fragmented. Having removed the old items from the shared memory area, additional overhead is expended to retrieve the old items from disk when subsequently required by server processes.
In addition to increasing the frequency of disk access, fragmentation may significantly increase the workload of a server process. For example, one or more users might repeatedly issue the same particular SQL statement. The first time the statement is executed, it is parsed and optimized, and the resulting parse tree and execution plan are stored in the shared memory area, where they remain available for subsequent executions of the statement. Fragmentation may cause these items to be removed from the shared memory area sooner than would be necessary if the shared memory area were less fragmented. After these items have been removed from the shared memory area, the statement must be parsed and optimized again the next time it is received.
One technique for lessening the performance impact of fragmentation of the shared memory area is the "paging" technique. Paging involves dividing items that are to be loaded in the shared memory area into blocks called pages. Each of the pages can be loaded into a different area of the shared memory area, that, without paging, is individually too small to be used to allocate to store the entire item. Paging thus reduces the frequency at which items are removed from the shared memory area.
One approach for paging is the "uniform-page-size" approach. In the uniform-page-size approach, uniformly sized pages of an item are loaded into free space within the shared memory area at runtime. The memory area into which a given page of the item is loaded is contiguous, but the memory areas that hold the various pages of a given item may not be contiguous with respect to each other.
In a shared memory area within a virtual memory address space, it is possible that a page may be stored in a contiguous range of virtual memory but be split between multiple physical regions of memory. Such splitting of pages between physical regions of memory is invisible to applications that only "see" virtual memory and is an issue that is addressed by the operating system.
The uniform-page-size approach works well for items that can be easily divided into equal sized pages without splitting individual components within the items. For example, byte code of a stored PL/SQL program unit includes byte code instructions for one or more routines. Because the byte code instructions are relatively small, the byte code module can easily be divided into equal sized pages without splitting a byte code instruction between pages.
The uniform-page size approach does not work well for items that contain large sub-items, or where there is a large variation in the sizes of sub-items. For example, one of the items that is loaded into the shared memory area when a PL/SQL.RTM. program is executed is the constant pool associated with the unit. A constant pool is a set of data structures containing data that remains fixed throughout the execution of a program unit. Constant pools may contain, among other things: string constants, information for exception handlers, data type descriptors for PL/SQL.TM. data types, and PL/SQL function call descriptors (metadata describing a called function). For example, a constant pool for a program that prints text, named PrintText, may contain a function descriptor describing an invocation of the function `print`. The function descriptors are then followed by a set of constant strings, which represent the text to print.
Sometimes, the string constants contained in a constant pool are too large to fit into a page. When this occurs, the string constant must be split between two pages. Unfortunately, when it is possible for portions of a sub-item, such as a PL/SQL.TM. string, to be stored at two non-contiguous regions of the shared memory area, the overhead associated with accessing the item is significantly increased. Specifically, the split sub-items must be reconstructed when they are accessed by a process.
For example, assume the constant pool associated with PrintText contains a string, boilerPlate, representing boilerplate text for a purchase order, and that the string size is 4.5 kbytes. The size of a data structure, as used herein, indicates the amount of computer memory required to store the data structure. Further assume that the size of the page is 4 kbytes. The string boilerPlate, being bigger than 4 kbytes, must be split between two pages. Typically, when a process accesses a string, the string must be presented as one contiguous stream of characters that ends with a terminating character. In order to make the string appear in this manner, the string is reconstructed by combining the split portions and storing them together, temporarily, in a separate contiguous area of memory. Reconstructing a string thus requires operations for allocating a contiguous area memory, accessing the split portions, combining and storing them in the allocated contiguous area of memory, and then de-allocating the memory. Performing these operations causes an undesirable level of overhead.
Based on the foregoing, it would be highly desirable to provide a method of paging which avoids the inefficiency inherent in splitting sub-items between pages.